class Solution
{
public:
    // 贪心法, 正确性比较难想, 但确实是对的
    int maxIncreasingGroups(vector<int> &usageLimits)
    {
        sort(usageLimits.begin(), usageLimits.end());
        vector<long long> remain(usageLimits.begin(), usageLimits.end());
        int n = usageLimits.size();
        long long result = 0;
        for (int i = 0; i < n; ++i)
        {
            if (remain[i] > result)
            {
                ++result;
                remain[i] -= result;
            }
            if (remain[i] > 0 && i + 1 < n)
            {
                remain[i + 1] += remain[i];
            }
        }
        return result;
    }

    // 这个答案是错的, 验证的方法不对
    int maxIncreasingGroups(vector<int> &usageLimits)
    {
        sort(usageLimits.rbegin(), usageLimits.rend());

        // 二分答案n, 验证一个答案n是否可行需要 O(n) 的时间
        int left = 1;
        int right = usageLimits.size();

        auto check = [&](int groupCount)
        {
            for (int i = 0; i < groupCount; ++i)
            {
                if (usageLimits[i] < groupCount - i)
                {
                    return false;
                }
            }
            return true;
        };
        while (left < right)
        {
            int mid = (left + right + 1) / 2;
            if (check(mid))
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left;
    }
};